{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Closed Number LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findClosedNumbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #下一个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>下一个数。给定一个正整数，找出与其二进制表达式中1的个数相同且大小最接近的那两个数（一个略大，一个略小）。</p>\n",
    "\n",
    "<p> <strong>示例1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong> 输入</strong>：num = 2（或者0b10）\n",
    "<strong> 输出</strong>：[4, 1] 或者（[0b100, 0b1]）\n",
    "</pre>\n",
    "\n",
    "<p> <strong>示例2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong> 输入</strong>：num = 1\n",
    "<strong> 输出</strong>：[2, -1]\n",
    "</pre>\n",
    "\n",
    "<p> <strong>提示:</strong></p>\n",
    "\n",
    "<ol>\n",
    "<li><code>num</code>的范围在[1, 2147483647]之间；</li>\n",
    "<li>如果找不到前一个或者后一个满足条件的正数，那么输出 -1。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [closed-number-lcci](https://leetcode.cn/problems/closed-number-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [closed-number-lcci](https://leetcode.cn/problems/closed-number-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        if num == 2147483647:\n",
    "            return [-1, -1]\n",
    "        ans = []\n",
    "        c = bin(num).count(\"1\")\n",
    "        suf = num + 1\n",
    "        while suf < 2147483648:\n",
    "            sc = bin(suf).count(\"1\")\n",
    "            if sc == c:\n",
    "                ans.append(suf)\n",
    "                break\n",
    "            suf += 1\n",
    "        if suf == 2147483648:\n",
    "            ans.append(-1)\n",
    "        pre = num - 1\n",
    "        while pre > 0:\n",
    "            pc = bin(pre).count(\"1\")\n",
    "            if pc == c:\n",
    "                ans.append(pre)\n",
    "                break\n",
    "            pre -= 1\n",
    "        if len(ans) == 2:\n",
    "            return ans\n",
    "        return ans + [-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        if num == (1<<31) - 1 or num == 0xffffffff:\n",
    "            return [-1, -1]\n",
    "        larger, smaller = -1, -1\n",
    "        cnt = 0\n",
    "        for i in range(31):\n",
    "            if num&(1<<i) and not num&(1<<(i+1)):\n",
    "                larger = (num&(0xffffffff<<(i+1))) | (1<<(i+1)) | ((1<<cnt)-1)\n",
    "                break\n",
    "            elif num&(1<<i):\n",
    "                cnt += 1\n",
    "        cnt = 0\n",
    "        for i in range(31):\n",
    "            if not num&(1<<i) and num&(1<<(i+1)):\n",
    "                smaller = (num&(0xffffffff<<(i+2))) | (((1<<(cnt+1))-1)<<(i-cnt))\n",
    "                break\n",
    "            elif num&(1<<i):\n",
    "                cnt += 1\n",
    "        return [larger, smaller]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        b=str(bin(num))[2:]\n",
    "        if not '0' in b:\n",
    "            if len(b)==31:\n",
    "                return [-1,-1]\n",
    "            else:\n",
    "                return [int('0b10'+b[1:],2),-1]\n",
    "        b='0'+b\n",
    "        smaller,bigger=None,None\n",
    "        for i in range(len(b)-1,-1,-1):\n",
    "            if b[i:i+2]=='10':\n",
    "                tmp=b[i+2:]\n",
    "                tmp='1'*tmp.count('1')+'0'*tmp.count('0')\n",
    "                smaller=b[:i]+'01'+tmp\n",
    "                break\n",
    "        for i in range(len(b)-1,-1,-1):\n",
    "            if b[i:i+2]=='01':\n",
    "                tmp=b[i+2:]\n",
    "                tmp='0'*tmp.count('0')+'1'*tmp.count('1')\n",
    "                bigger=b[:i]+'10'+tmp\n",
    "                break\n",
    "        return [int(bigger, 2), int(smaller, 2)]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_small(self, bit1):\n",
    "        # 找出第一个1且其左边还有0\n",
    "        loc1 = -1\n",
    "        loc0 = -1\n",
    "        for i in range(len(bit1)):\n",
    "            if bit1[i]==1 and 0 in bit1[:i]:\n",
    "                loc1 = i\n",
    "                break\n",
    "        # 找到左边离这个1最近的0\n",
    "        for i in range(loc1):\n",
    "            if bit1[i]==0:\n",
    "                loc0 = i\n",
    "        small = 0\n",
    "        if loc0==-1 or loc1 == -1: # 如果没有找到\n",
    "            small = -1\n",
    "        else: # 找到了\n",
    "            # 将最低位的1交换到最高位的0\n",
    "            bit1[loc0] = 1\n",
    "            bit1[loc1] = 0\n",
    "            # 将低于loc0位的1与0交换(把1交换到高位，相距最远的0和1交换)\n",
    "            low, high = 0, loc0-1\n",
    "            while low<high:\n",
    "                if bit1[low] == 1:\n",
    "                    while high>low:\n",
    "                        if bit1[high]==0:\n",
    "                            bit1[high]=1\n",
    "                            bit1[low]=0\n",
    "                            low+=1\n",
    "                            high-=1\n",
    "                            break\n",
    "                        high-=1\n",
    "                else:\n",
    "                    low+=1\n",
    "\n",
    "            for i in range(len(bit1)):\n",
    "                small += bit1[i]<<i\n",
    "        return small\n",
    "\n",
    "    def get_big(self, bit1):\n",
    "        # 找出第一个0且其左边有1\n",
    "        loc1 = -1\n",
    "        loc0 = -1\n",
    "        for i in range(len(bit1)):\n",
    "            if bit1[i]==0 and 1 in bit1[:i]:\n",
    "                loc0 = i\n",
    "                break\n",
    "\n",
    "        # 找出离这个0最近的1\n",
    "        for i in range(loc0):\n",
    "            if bit1[i]==1:\n",
    "                loc1 = i\n",
    "        \n",
    "        big = 0\n",
    "        if loc0==-1 or loc1 == -1:\n",
    "            big = -1\n",
    "        else:\n",
    "            bit1[loc0] = 1\n",
    "            bit1[loc1] = 0\n",
    "            # 将低于loc0位的1与0交换(把1交换到低位，相距最远的0和1交换)\n",
    "            low, high = 0, loc0-1\n",
    "            while low<high:\n",
    "                if bit1[low] == 0:\n",
    "                    while high>low:\n",
    "                        if bit1[high]==1:\n",
    "                            bit1[high]=0\n",
    "                            bit1[low]=1\n",
    "                            low+=1\n",
    "                            high-=1\n",
    "                            break\n",
    "                        high-=1\n",
    "                else:\n",
    "                    low+=1\n",
    "            for i in range(len(bit1)):\n",
    "                big += bit1[i]<<i\n",
    "\n",
    "        return big\n",
    "\n",
    "\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        bit1 = [0]*31\n",
    "        for i in range(len(bit1)):\n",
    "            if num & 1<<i != 0: \n",
    "                bit1[i]=1\n",
    "        small = self.get_small(bit1[:])\n",
    "        big = self.get_big(bit1[:])\n",
    "        return [big, small] \n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        if num == 0x7fffffff:\n",
    "            return [-1, -1]\n",
    "        num_bin = bin(num).replace('b', 'b0')[::-1]\n",
    "        res = [0] * 2\n",
    "        idx = num_bin.find(\"10\")\n",
    "        ones = num_bin.count('1', 0, idx)\n",
    "        res[0] = int(('1' * ones + '0' * (idx - ones) + \"01\" + num_bin[idx + 2:])[::-1], base=2)\n",
    "        idx = num_bin.find(\"01\")\n",
    "        if idx == -1:\n",
    "            res[1] = -1\n",
    "        else:\n",
    "            ones = num_bin.count('1', 0, idx)\n",
    "            res[1] = int(('0' * (idx - ones) + '1' * ones + \"10\" + num_bin[idx + 2:])[::-1], base=2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        def getDigit(num):\n",
    "            digit = []\n",
    "            while(num > 0):\n",
    "                digit.append(num % 2)\n",
    "                num = num // 2\n",
    "            return digit[::-1]\n",
    "        def getNum(digit):\n",
    "            n = len(digit)\n",
    "            num = 0\n",
    "            for i in range(n):\n",
    "                num += digit[i]*2**(n-1-i)\n",
    "            return num\n",
    "\n",
    "        digit = getDigit(num)\n",
    "        n = len(digit)\n",
    "        #find bigger\n",
    "        ones = 0\n",
    "        idx1 = None\n",
    "        idx0 = None\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if(digit[i] == 1):\n",
    "                if(ones == 0):\n",
    "                    idx1 = i\n",
    "                ones += 1\n",
    "            else:\n",
    "                if(ones > 0):\n",
    "                    idx0 = i \n",
    "                    break\n",
    "        if(idx0 == None):\n",
    "            bigger = [1,0] + digit[1:][::-1]\n",
    "        else:\n",
    "            bigger = digit[:]\n",
    "            bigger[idx0] = 1\n",
    "            ones -= 1\n",
    "            for i in range(n-1,idx0,-1):\n",
    "                if(ones > 0):\n",
    "                    bigger[i] = 1\n",
    "                    ones -= 1\n",
    "                else:\n",
    "                    bigger[i] = 0\n",
    "        bigger = getNum(bigger)\n",
    "        if(bigger >= 2147483647):\n",
    "            bigger = -1\n",
    "        #find smaller\n",
    "        zeros = 0\n",
    "        idx0 = None\n",
    "        idx1 = None\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if(digit[i] == 0):\n",
    "                if(zeros == 0):\n",
    "                    idx0 = i\n",
    "                zeros += 1\n",
    "            else:\n",
    "                if(zeros > 0):\n",
    "                    idx1 = i \n",
    "                    break\n",
    "        if(idx1 == None):\n",
    "            smaller = -1\n",
    "        else:\n",
    "            smaller = digit[:]\n",
    "            smaller[idx1] = 0\n",
    "            zeros -= 1\n",
    "            for i in range(n-1,idx1,-1):\n",
    "                if(zeros > 0):\n",
    "                    smaller[i] = 0\n",
    "                    zeros -= 1\n",
    "                else:\n",
    "                    smaller[i] = 1\n",
    "            smaller = getNum(smaller)\n",
    "        # print(digit)\n",
    "        # print(bigger,getDigit(bigger))\n",
    "        # print(smaller,getDigit(smaller))\n",
    "        return [bigger, smaller]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "\n",
    "        samenum=num\n",
    "        bin_num=bin(num)[2:]\n",
    "        out_list=[-1,-1]\n",
    "        alen=len(bin_num)\n",
    "\n",
    "        #找小的\n",
    "        i=-1\n",
    "        count1=0\n",
    "        for i in range(alen-1,0,-1):\n",
    "            if bin_num[i]==\"1\":\n",
    "                count1+=1\n",
    "            if bin_num[i]==\"0\" and bin_num[i-1]==\"1\":\n",
    "                break\n",
    "        if i!=-1 and bin_num[i]==\"0\" and bin_num[i-1]==\"1\":\n",
    "            out_list[1]=int(bin_num[:i-1]+\"01\"+\"1\"*count1+\"0\"*(alen-1-i-count1),2)\n",
    "\n",
    "        #找大的\n",
    "        j=-1\n",
    "        count0=0\n",
    "        for j in range(alen-1,0,-1):\n",
    "            if bin_num[j]==\"1\" and bin_num[j-1]==\"0\":\n",
    "                break\n",
    "            if bin_num[j]==\"0\":\n",
    "                count0+=1\n",
    "        if j!=-1 and bin_num[j]==\"1\" and bin_num[j-1]==\"0\":\n",
    "            out_list[0]=int(bin_num[:j-1]+\"10\"+\"0\"*count0+\"1\"*(alen-1-j-count0),2)\n",
    "        elif alen<31 :\n",
    "            out_list[0]=int(\"10\"+\"0\"*count0+\"1\"*(alen-1-count0),2)\n",
    "            \n",
    "\n",
    "        return  out_list\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        if num == 1:\n",
    "            return [2, -1]\n",
    "        if num == 2147483647:\n",
    "            return [-1, -1]\n",
    "        \n",
    "        s = bin(num)[2:].zfill(32)\n",
    "        ret = []\n",
    "        print(bin(num))\n",
    "        # larger\n",
    "        if \"01\" in s:\n",
    "            index = s.rfind(\"01\")\n",
    "            ans = s[:index] + \"10\" + \"\".join(sorted(s[index+2:]))\n",
    "            print(f\"ans = {ans}\")\n",
    "            ret.append(int(ans, base=2))\n",
    "        else:\n",
    "            ret.append(-1)\n",
    "\n",
    "        # smaller\n",
    "        if \"10\" in s:\n",
    "            index = s.rfind(\"10\")\n",
    "            ans = s[:index] + \"01\" + \"\".join(sorted(s[index+2:], reverse=True))\n",
    "            ret.append(int(ans, base=2))\n",
    "        else:\n",
    "            ret.append(-1)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        res = [-1] * 2\n",
    "        ones = bits = 0\n",
    "        while bits < 31 and not (1 << bits & num):\n",
    "            bits += 1\n",
    "        while bits < 31 and 1 << bits & num:\n",
    "            bits += 1\n",
    "            ones += 1\n",
    "        if bits != 31:\n",
    "            res[0] = ((num | 1 << bits) & ~((1 << bits) - 1)) | ((1 << (ones - 1)) - 1)\n",
    "        ones = bits = 0\n",
    "        while bits < 31 and 1 << bits & num:\n",
    "            bits += 1\n",
    "            ones += 1\n",
    "        while bits < 31 and not (1 << bits & num):\n",
    "            bits += 1\n",
    "        if bits != 31:\n",
    "            res[1] = (num & ~(1 << bits) | ((1 << bits) - 1)) & ~((1 << (bits - ones - 1)) - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        mn, mx = 1, 2147483647\n",
    "\n",
    "        def findLarge(n):\n",
    "            # 从右开始找到第1个1\n",
    "            # 然后记录1的个数ones直到再遇到0或到最高位\n",
    "            # 然后将这个0变成1\n",
    "            # 然后右边的位数用000...111(ones-1个1)填充\n",
    "            checkMask = 1\n",
    "            bits = 0\n",
    "            while checkMask <= n and checkMask & n == 0:\n",
    "                checkMask <<= 1\n",
    "                bits += 1\n",
    "            ones = 0  # 直接构造出000...111\n",
    "            while checkMask <= n and checkMask & n != 0:\n",
    "                ones = (ones << 1) + 1\n",
    "                checkMask <<= 1\n",
    "                bits += 1\n",
    "            # 因为在改变的位已经将1个0转成1了, 所以这里ones要向右移动一位\n",
    "            ones >>= 1\n",
    "            # 将0转成1\n",
    "            n |= checkMask\n",
    "            # 清除右边的0\n",
    "            n = (n >> bits) << bits\n",
    "            # 将右边填充上ones\n",
    "            n |= ones\n",
    "            return n if mn <= n <= mx else -1\n",
    "\n",
    "        def findSmall(n):\n",
    "            # 从右开始找到第1个0, 记录此过程1的个数ones\n",
    "            # 然后继续往左找直到再遇到1\n",
    "            # 然后将这个1变成0, ones也要左移一位(也可以初始化为1)\n",
    "            # 然后右边的位数用高位ones个1填充, 即构造出111...000, 可以直接基于ones构造\n",
    "            # 注意如果全为1的话是无解的, 直接返回-1\n",
    "            checkMask = 1\n",
    "            bits = 0\n",
    "            ones = 1\n",
    "            while checkMask <= n and checkMask & n != 0:\n",
    "                checkMask <<= 1\n",
    "                bits += 1\n",
    "                ones = (ones << 1) + 1\n",
    "            if checkMask > n:\n",
    "                # 全部是1\n",
    "                return -1\n",
    "            while checkMask <= n and checkMask & n == 0:\n",
    "                checkMask <<= 1\n",
    "                bits += 1\n",
    "                ones <<= 1\n",
    "            # 因为ones初始化为1, 所以ones需要右移一位\n",
    "            ones >>= 1\n",
    "            # 将需要改变的1变成0\n",
    "            n &= ~checkMask\n",
    "            # 清除右边的0\n",
    "            n = (n >> bits) << bits\n",
    "            # 将右边填充上ones\n",
    "            n |= ones\n",
    "            return n if mn <= n <= mx else -1\n",
    "\n",
    "        return [findLarge(num), findSmall(num)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        last_num = -1\n",
    "        next_num = -1\n",
    "        b = 2\n",
    "        while b < 1 << 31 and not (num & b != 0 and num & (b >> 1) == 0):\n",
    "            b <<= 1\n",
    "        if b < 1 << 31:\n",
    "            cnt = 1\n",
    "            t = 1\n",
    "            while t < b:\n",
    "                if num & t:\n",
    "                    cnt += 1\n",
    "                t <<= 1\n",
    "            last_num = num & ~((b << 1) - 1)\n",
    "            t = b >> 1\n",
    "            while cnt:\n",
    "                last_num |= t\n",
    "                cnt -= 1\n",
    "                t >>= 1\n",
    "        b = 2\n",
    "        while b < 1 << 31 and not (num & b == 0 and num & (b >> 1) != 0):\n",
    "            b <<= 1\n",
    "        if b < 1 << 31:\n",
    "            cnt = 0\n",
    "            t = 1\n",
    "            while t < b >> 1:\n",
    "                if num & t:\n",
    "                    cnt += 1\n",
    "                t <<= 1\n",
    "            next_num = num | b\n",
    "            next_num &= ~(b - 1)\n",
    "            t = 1\n",
    "            while cnt:\n",
    "                next_num |= t\n",
    "                cnt -= 1\n",
    "                t <<= 1\n",
    "        return [next_num, last_num]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        idx = 0\n",
    "        while num & (1<<idx)==0:\n",
    "            idx += 1\n",
    "        \n",
    "        jdx = idx\n",
    "        while num & (1<<jdx):\n",
    "            jdx += 1\n",
    "        \n",
    "        num1 = jdx - idx\n",
    "        mask1 = (1<<jdx)-1\n",
    "        larger = num & (~mask1)\n",
    "        larger |= (1<<jdx)\n",
    "        mask2 = (1<<(num1-1))-1\n",
    "        larger |= mask2\n",
    "\n",
    "\n",
    "        idx = 0\n",
    "        while num & (1<<idx):\n",
    "            idx += 1\n",
    "        \n",
    "        num1 = idx\n",
    "        jdx = idx\n",
    "        while (1<<jdx)<=num and num&(1<<jdx) == 0:\n",
    "            jdx += 1\n",
    "        \n",
    "        if (1<<jdx) > num:\n",
    "            smaller = -1\n",
    "        else:\n",
    "            mask1 = (1<<(jdx+1))-1\n",
    "            smaller = num & (~mask1)\n",
    "            mask2 = (1<<jdx)-1\n",
    "            mask3 = (1<<(jdx-num1-1))-1\n",
    "            smaller |= (mask2 - mask3)\n",
    "        \n",
    "        return [larger if larger <= (1<<31)-1 else -1, smaller]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        res = [-1] * 2\n",
    "        ones = bits = 0\n",
    "        while bits < 31 and not (1 << bits & num):\n",
    "            bits += 1\n",
    "        while bits < 31 and 1 << bits & num:\n",
    "            bits += 1\n",
    "            ones += 1\n",
    "        if bits != 31:\n",
    "            res[0] = ((num | 1 << bits) & ~((1 << bits) - 1)) | ((1 << (ones - 1)) - 1)\n",
    "        ones = bits = 0\n",
    "        while bits < 31 and 1 << bits & num:\n",
    "            bits += 1\n",
    "            ones += 1\n",
    "        while bits < 31 and not (1 << bits & num):\n",
    "            bits += 1\n",
    "        if bits != 31:\n",
    "            res[1] = (num & ~(1 << bits) | ((1 << bits) - 1)) & ~((1 << (bits - ones - 1)) - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        if num == 2147483647:\n",
    "            return [-1, -1]\n",
    "        if num == 1:\n",
    "            return [2, -1]\n",
    "        def fb(n, a):\n",
    "            c = j = 0\n",
    "            while n >> j & 1 == a:\n",
    "                j += 1\n",
    "            while n >> j & 1 != a:\n",
    "                n ^= (1 << j) ^ (1 << c)\n",
    "                j += 1\n",
    "                c += 1\n",
    "            return n ^ (1 << j) ^ (1 << (c - 1))\n",
    "        return [fb(num, 0), fb(num, 1)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        # 转化成二进制字母\n",
    "        def num2bin(num):\n",
    "            bin = \"\"\n",
    "            while num != 0:\n",
    "                bin = str(num%2) + bin\n",
    "                num //= 2\n",
    "            return bin\n",
    "        \n",
    "        def bin2num(bin):\n",
    "            num = 0\n",
    "            k = 0\n",
    "            for i in bin[::-1]:\n",
    "                num += int(i) * 2 ** k\n",
    "                k += 1\n",
    "            return num\n",
    "        bin = num2bin(num)\n",
    "        print(bin)\n",
    "        bin1 = bin\n",
    "        # 寻找最小的那个正数\n",
    "        x = bin[::-1]\n",
    "        zeroidx = -1\n",
    "        for i in range(len(bin)-1): \n",
    "            if x[i:i+2] == \"01\":\n",
    "                zeroidx = i\n",
    "                break\n",
    "        if zeroidx == -1:\n",
    "            minO = -1\n",
    "        else:\n",
    "            s1 = list(bin)\n",
    "            s1[len(bin) - zeroidx - 2] = \"0\"\n",
    "            s1[len(bin) - zeroidx - 1] = \"1\"\n",
    "            onenumber = 0\n",
    "            for i in range(len(bin) - zeroidx,len(bin)):\n",
    "                if s1[i] == \"1\":\n",
    "                    onenumber += 1\n",
    "            s1 = s1[:len(bin) - zeroidx]\n",
    "            s1.extend([\"1\"]*onenumber)\n",
    "            s1.extend([\"0\"]*(zeroidx - onenumber))\n",
    "            minO = bin2num(\"\".join(s1))\n",
    "        if num >= 2147483647:\n",
    "            return [-1,minO ]\n",
    "        zeroidx = -1\n",
    "        for i in range(len(bin)-1): \n",
    "            if x[i:i+2] == \"10\":\n",
    "                zeroidx = i\n",
    "                break\n",
    "        if zeroidx == -1:\n",
    "            s1 = list(bin)\n",
    "            s1[0] = \"0\"\n",
    "            s2 = \"10\"\n",
    "            onenumber = 0\n",
    "            for i in range(len(bin)):\n",
    "                if s1[i] == \"1\":\n",
    "                    onenumber += 1\n",
    "            s2 += \"0\"*(len(bin) - onenumber-1) + \"1\"*(onenumber)\n",
    "            # 1101110\n",
    "            maxO = bin2num(\"\".join(s2))\n",
    "        else:\n",
    "            s1 = list(bin)\n",
    "            s1[len(bin) - zeroidx - 2] = \"1\"\n",
    "            s1[len(bin) - zeroidx - 1] = \"0\"\n",
    "            onenumber = 0\n",
    "            for i in range(len(bin) - zeroidx,len(bin)):\n",
    "                if s1[i] == \"1\":\n",
    "                    onenumber += 1\n",
    "            s1 = s1[:len(bin) - zeroidx]\n",
    "            s1.extend([\"0\"]*(zeroidx - onenumber))\n",
    "            s1.extend([\"1\"]*onenumber)\n",
    "            \n",
    "            print(\"\".join(s1))\n",
    "            print(num2bin(69))\n",
    "            maxO = bin2num(\"\".join(s1))\n",
    "        \n",
    "        return [maxO,minO]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        x = y = num\n",
    "        ans = [-1] * 2\n",
    "        for i in range(1, 31):\n",
    "            if (x >> i & 1) and (x >> (i - 1) & 1) == 0:\n",
    "                x ^= 1 << i\n",
    "                x ^= 1 << (i - 1)\n",
    "                j, k = 0, i - 2\n",
    "                while j < k:\n",
    "                    while j < k and (x >> j & 1) == 0:\n",
    "                        j += 1\n",
    "                    while j < k and (x >> k & 1) == 1:\n",
    "                        k -= 1\n",
    "                    if j < k:\n",
    "                        x ^= 1 << j\n",
    "                        x ^= 1 << k\n",
    "                ans[1] = x\n",
    "                break\n",
    "        x = num\n",
    "        for i in range(1, 31):\n",
    "            if (x >> i & 1) == 0 and x >> (i - 1) & 1:\n",
    "                x ^= 1 << i\n",
    "                x ^= 1 << (i - 1)\n",
    "                j, k = 0, i - 2\n",
    "                while j < k:\n",
    "                    while j < k and (x >> j & 1) == 1:\n",
    "                        j += 1\n",
    "                    while j < k and (x >> k & 1) == 0:\n",
    "                        k -= 1\n",
    "                    if j < k:\n",
    "                        x ^= 1 << j\n",
    "                        x ^= 1 << k\n",
    "                ans[0] = x\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        def getDigit(num):\n",
    "            digit = []\n",
    "            while(num > 0):\n",
    "                digit.append(num % 2)\n",
    "                num = num // 2\n",
    "            return digit[::-1]\n",
    "        def getNum(digit):\n",
    "            n = len(digit)\n",
    "            num = 0\n",
    "            for i in range(n):\n",
    "                num += digit[i]*2**(n-1-i)\n",
    "            return num\n",
    "\n",
    "        digit = getDigit(num)\n",
    "        n = len(digit)\n",
    "        #find bigger\n",
    "        ones = 0\n",
    "        idx1 = None\n",
    "        idx0 = None\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if(digit[i] == 1):\n",
    "                if(ones == 0):\n",
    "                    idx1 = i\n",
    "                ones += 1\n",
    "            else:\n",
    "                if(ones > 0):\n",
    "                    idx0 = i \n",
    "                    break\n",
    "        if(idx0 == None):\n",
    "            bigger = [1,0] + digit[1:][::-1]\n",
    "        else:\n",
    "            bigger = digit[:]\n",
    "            bigger[idx0] = 1\n",
    "            ones -= 1\n",
    "            for i in range(n-1,idx0,-1):\n",
    "                if(ones > 0):\n",
    "                    bigger[i] = 1\n",
    "                    ones -= 1\n",
    "                else:\n",
    "                    bigger[i] = 0\n",
    "        bigger = getNum(bigger)\n",
    "        if(bigger >= 2147483647):\n",
    "            bigger = -1\n",
    "        #find smaller\n",
    "        zeros = 0\n",
    "        idx0 = None\n",
    "        idx1 = None\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if(digit[i] == 0):\n",
    "                if(zeros == 0):\n",
    "                    idx0 = i\n",
    "                zeros += 1\n",
    "            else:\n",
    "                if(zeros > 0):\n",
    "                    idx1 = i \n",
    "                    break\n",
    "        if(idx1 == None):\n",
    "            smaller = -1\n",
    "        else:\n",
    "            smaller = digit[:]\n",
    "            smaller[idx1] = 0\n",
    "            zeros -= 1\n",
    "            for i in range(n-1,idx1,-1):\n",
    "                if(zeros > 0):\n",
    "                    smaller[i] = 0\n",
    "                    zeros -= 1\n",
    "                else:\n",
    "                    smaller[i] = 1\n",
    "            smaller = getNum(smaller)\n",
    "        # print(digit)\n",
    "        # print(bigger,getDigit(bigger))\n",
    "        # print(smaller,getDigit(smaller))\n",
    "        return [bigger, smaller]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        if num==2147483647: return [-1,-1]\n",
    "        def func(n,s1,s2):\n",
    "            a=list(bin(n))\n",
    "            a.insert(2,'0')\n",
    "            for i in range(len(a)-1,1,-1):\n",
    "                if a[i]==s1 and i!=len(a)-1 and a[i+1]==s2:\n",
    "                    a[i],a[i+1]=a[i+1],a[i]\n",
    "                    j=0\n",
    "                    while i+2+j<len(a)-j and a[i+2+j]==s2 and a[-1-j]==s1:\n",
    "                        a[i+2+j],a[-1-j]=a[-1-j],a[i+2+j]\n",
    "                        j+=1\n",
    "                    return int(''.join(a),2)\n",
    "            return -1\n",
    "        return [func(num,'0','1'),func(num,'1','0')]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        if num == 2147483647:\n",
    "            return [-1, -1]\n",
    "        if num & 1:\n",
    "            t = 1\n",
    "            a = b = 0\n",
    "            while t <= num and num & t:\n",
    "                t = t * 2\n",
    "            if t > num:\n",
    "                return [t // 2 + num, -1]\n",
    "            a = t\n",
    "            while t <= num and not num & t:\n",
    "                t = t * 2\n",
    "            b = t\n",
    "            m = num + a // 2\n",
    "            k = num % a\n",
    "            n = (num - b // 2) ^ k \n",
    "            n = n + k * (b // a // 2)\n",
    "            return [m, n]\n",
    "        else:\n",
    "            t = 1\n",
    "            a = b = 0\n",
    "            while t <= num and not num & t:\n",
    "                t = t * 2\n",
    "            a = t\n",
    "            while t <= num and num & t:\n",
    "                t = t * 2\n",
    "            b = t\n",
    "            n = num - a // 2\n",
    "            k = num % (b // 2)\n",
    "            # print(a)\n",
    "            m = (num + b // 2) ^ k \n",
    "            m = m + k // a\n",
    "            return [m, n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        \"\"\"\n",
    "        变大：最后一个01变为10，后续1右靠，未找到返回-1\n",
    "        变小：最后一个10变为01，后续1左靠，未找到返回-1\n",
    "        \"\"\"\n",
    "        remin, remax = 0,0\n",
    "        imin,flag,imin1 = 0, False, 0\n",
    "        for i in range(32):\n",
    "            acc = (num>>i)&1\n",
    "            if not flag and acc==0:\n",
    "                flag = True\n",
    "            if acc==1:\n",
    "                if not flag:\n",
    "                    imin1+=1\n",
    "                else:\n",
    "                    imin = i\n",
    "                    break\n",
    "        remin = ((num^(1<<imin))&(~((1<<imin)-1)))|(((1<<(imin1+1))-1)<<(imin-imin1-1)) if imin>imin1 else -1\n",
    "        flag, imax, imax1 = False, 0, 0\n",
    "        for i in range(32):\n",
    "            acc = (num>>i)&1\n",
    "            if acc==1:\n",
    "                imax1+=1\n",
    "                flag = True\n",
    "            if flag and acc==0:\n",
    "                imax = i\n",
    "                break\n",
    "        remax = ((num|(1<<imax))&(~((1<<imax)-1)))|((1<<(imax1-1))-1) if imax<31 else -1\n",
    "        return [remax,remin]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        left=index1=-1\n",
    "        right=index2=-1\n",
    "        result=[]\n",
    "\n",
    "        temp=num\n",
    "        left_index=0\n",
    "        while temp!=0:\n",
    "            if temp&1==0:\n",
    "                index1=1\n",
    "            elif temp&1==1 and index1==1:\n",
    "                left=left_index\n",
    "                break\n",
    "            temp>>=1\n",
    "            left_index+=1\n",
    "\n",
    "        \n",
    "        temp=num\n",
    "        for i in range(31):\n",
    "            if temp&1==1:\n",
    "                index2=1\n",
    "            elif temp&1==0 and index2==1:\n",
    "                right=i\n",
    "                break\n",
    "            temp>>=1\n",
    "\n",
    "\n",
    "        temp=num \n",
    "        if right!=-1:\n",
    "            temp-=(1<<(right-1))\n",
    "            temp+=(1<<right)\n",
    "            \n",
    "            index_left=0\n",
    "            count=0\n",
    "            while index_left<right-1:\n",
    "                if temp&(1<<index_left):\n",
    "                    temp&=(temp-1)\n",
    "                    count+=1\n",
    "                index_left+=1\n",
    "            \n",
    "            for i in range(count):\n",
    "                temp+=(1<<i)\n",
    "            result.append(temp)\n",
    "        else:\n",
    "            result.append(-1)\n",
    "            \n",
    "\n",
    "        temp=num\n",
    "        if index1!=-1:\n",
    "            temp-=(1<<left)\n",
    "            temp+=(1<<(left-1))\n",
    "\n",
    "            index_right=0\n",
    "            count=0\n",
    "            while index_right<left-1:\n",
    "                if temp&(1<<index_right):\n",
    "                    temp&=(temp-1)\n",
    "                    count+=1\n",
    "                index_right+=1\n",
    "            \n",
    "            for j in range(count):\n",
    "                temp+=(1<<(left-2-j))\n",
    "            result.append(temp)\n",
    "        else:\n",
    "            result.append(-1)\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        i = 0\n",
    "        enter = False\n",
    "        temp = num\n",
    "        bits = []\n",
    "        found = False\n",
    "        # 遍历数字比特位，并查找第一段连续的 0 比特位区域\n",
    "        # 停止条件：\n",
    "        # 1. 遇到 0 比特位后的首个 1\n",
    "        # 2. 遍历完数字 num 的所有位：num 为 全 1\n",
    "        while temp:\n",
    "            if not (temp & 1):\n",
    "                enter = True\n",
    "            else:\n",
    "                bits.append(i)\n",
    "                if enter: # 0 比特位后的首个 1\n",
    "                    break\n",
    "            temp = temp >> 1\n",
    "            i += 1\n",
    "        else:\n",
    "            found = True\n",
    "            lower = -1\n",
    "        if not found:\n",
    "            # 将 0 左边的首位 1 向右移动一位(即 0 区域的最高位)\n",
    "            pos_1_after_0 = bits.pop()\n",
    "            lower = num - 2 ** (pos_1_after_0 - 1)\n",
    "            # 将 0 右边的 1 向左移动（移动到的最高位为 0 区域的次高位）\n",
    "            bits = bits[::-1]\n",
    "            pos = range(pos_1_after_0-2, pos_1_after_0-2-len(bits), -1)\n",
    "            for i,p in zip(bits, pos):\n",
    "                lower = (lower ^ (2 ** i)) | 2 ** p\n",
    "\n",
    "        i = 0\n",
    "        enter = False\n",
    "        temp = num\n",
    "        bits = []\n",
    "        # 遍历数字比特位，并查找第一段连续的 1 比特位区域\n",
    "        # 停止条件：\n",
    "        # 1. 遇到 1 比特位后的首个 0\n",
    "        # 2. 遍历完数字 num 的所有位：num 为 全 1 或者 1xx000 的形式（x 为 1）\n",
    "        while temp:\n",
    "            if temp & 1:\n",
    "                enter = True\n",
    "                bits.append(i)\n",
    "            else:\n",
    "                if enter : # 1 比特位后的首个 0\n",
    "                    break\n",
    "            temp = temp >> 1\n",
    "            i += 1\n",
    "        # 将该段 1 的最高位 1 向左移动 1 位\n",
    "        upper = num + 2 ** bits.pop()\n",
    "        # 该段 1 的剩余 1 向右移动到最低位\n",
    "        pos = range(len(bits))\n",
    "        for i,p in zip(bits, pos):\n",
    "            upper = (upper ^ (2 ** i)) | (2 ** p)\n",
    "        if upper > 2147483647:\n",
    "            upper = -1\n",
    "\n",
    "        return [upper, lower]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        mn, mx = 1, 2147483647\n",
    "\n",
    "        def findLarge(n):\n",
    "            # 从右开始找到第1个1\n",
    "            # 然后记录1的个数ones直到再遇到0或到最高位\n",
    "            # 然后将这个0变成1\n",
    "            # 然后右边的位数用000...111(ones-1个1)填充\n",
    "            checkMask = 1\n",
    "            bits = 0\n",
    "            while checkMask <= n and checkMask & n == 0:\n",
    "                checkMask <<= 1\n",
    "                bits += 1\n",
    "            ones = 0  # 直接构造出000...111\n",
    "            while checkMask <= n and checkMask & n != 0:\n",
    "                ones = (ones << 1) + 1\n",
    "                checkMask <<= 1\n",
    "                bits += 1\n",
    "            # 因为在改变的位已经将1个0转成1了, 所以这里ones要向右移动一位\n",
    "            ones >>= 1\n",
    "            # 将0转成1\n",
    "            n |= checkMask\n",
    "            # 清除右边的0\n",
    "            n = (n >> bits) << bits\n",
    "            # 将右边填充上ones\n",
    "            n |= ones\n",
    "            return n if mn <= n <= mx else -1\n",
    "\n",
    "        def findSmall(n):\n",
    "            # 从右开始找到第1个0, 记录此过程1的个数ones\n",
    "            # 然后继续往左找直到再遇到1\n",
    "            # 然后将这个1变成0, ones也要左移一位(也可以初始化为1)\n",
    "            # 然后右边的位数用高位ones个1填充, 即构造出111...000, 可以直接基于ones构造\n",
    "            # 注意如果全为1的话是无解的, 直接返回-1\n",
    "            checkMask = 1\n",
    "            bits = 0\n",
    "            ones = 1\n",
    "            while checkMask <= n and checkMask & n != 0:\n",
    "                checkMask <<= 1\n",
    "                bits += 1\n",
    "                ones = (ones << 1) + 1\n",
    "            if checkMask > n:\n",
    "                # 全部是1\n",
    "                return -1\n",
    "            while checkMask <= n and checkMask & n == 0:\n",
    "                checkMask <<= 1\n",
    "                bits += 1\n",
    "                ones <<= 1\n",
    "            # 因为ones初始化为1, 所以ones需要右移一位\n",
    "            ones >>= 1\n",
    "            # 将需要改变的1变成0\n",
    "            n &= ~checkMask\n",
    "            # 清除右边的0\n",
    "            n = (n >> bits) << bits\n",
    "            # 将右边填充上ones\n",
    "            n |= ones\n",
    "            return n if mn <= n <= mx else -1\n",
    "\n",
    "        return [findLarge(num), findSmall(num)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        remin, remax = 0,0\n",
    "        imin,flag,imin1 = 0, False, 0\n",
    "        for i in range(32):\n",
    "            acc = (num>>i)&1\n",
    "            if not flag and acc==0:\n",
    "                flag = True\n",
    "            if acc==1:\n",
    "                if not flag:\n",
    "                    imin1+=1\n",
    "                else:\n",
    "                    imin = i\n",
    "                    break\n",
    "        \n",
    "        remin = ((num^(1<<imin))&(~((1<<imin)-1)))|(((1<<(imin1+1))-1)<<(imin-imin1-1)) if imin>imin1 else -1\n",
    "        flag, imax, imax1 = False, 0, 0\n",
    "        for i in range(32):\n",
    "            acc = (num>>i)&1\n",
    "            if acc==1:\n",
    "                imax1+=1\n",
    "                flag = True\n",
    "            if flag and acc==0:\n",
    "                imax = i\n",
    "                break\n",
    "        remax = ((num|(1<<imax))&(~((1<<imax)-1)))|((1<<(imax1-1))-1) if imax<31 else -1\n",
    "        return [remax,remin]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        res = [-1] * 2\n",
    "        ones = bits = 0\n",
    "        while bits < 31 and not (1 << bits & num):\n",
    "            bits += 1\n",
    "        while bits < 31 and 1 << bits & num:\n",
    "            bits += 1\n",
    "            ones += 1\n",
    "        if bits != 31:\n",
    "            res[0] = ((num | 1 << bits) & ~((1 << bits) - 1)) | ((1 << (ones - 1)) - 1)\n",
    "        ones = bits = 0\n",
    "        while bits < 31 and 1 << bits & num:\n",
    "            bits += 1\n",
    "            ones += 1\n",
    "        while bits < 31 and not (1 << bits & num):\n",
    "            bits += 1\n",
    "        if bits != 31:\n",
    "            res[1] = (num & ~(1 << bits) | ((1 << bits) - 1)) & ~((1 << (bits - ones - 1)) - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "\n",
    "        def large(n):\n",
    "            zero = 0\n",
    "            i = 0\n",
    "            while i < 32 and n & (1 << i) == 0:\n",
    "                zero += 1\n",
    "                i += 1\n",
    "\n",
    "            one = 0\n",
    "            while i < 32 and n & (1 << i) != 0:\n",
    "                one += 1\n",
    "                i += 1\n",
    "            n |= 1 << i\n",
    "\n",
    "            n = (n >> i) << i\n",
    "            k = 0\n",
    "            for j in range(one-1):\n",
    "                k = k << 1 | 1\n",
    "            n |= k\n",
    "            return n if 1 <= n <= 2**31-1 else -1\n",
    "        \n",
    "        def small(n):\n",
    "            one = 1\n",
    "            i = 0\n",
    "            while i < 32 and n & (1 << i) != 0:\n",
    "                one += 1\n",
    "                i += 1\n",
    "\n",
    "            zero = 0\n",
    "            while i < 32 and n & (1 << i) == 0:\n",
    "                zero += 1\n",
    "                i += 1\n",
    "            n &= ~(1 << i)\n",
    "\n",
    "            n = (n >> i) << i\n",
    "            k = 0\n",
    "            for j in range(one):\n",
    "                k = k << 1 | 1\n",
    "            for j in range(zero-1):\n",
    "                k <<= 1\n",
    "            n |= k\n",
    "            return n if 1 <= n <= 2**31-1 else -1\n",
    "\n",
    "        return large(num), small(num)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        res = [-1] * 2\n",
    "        if num == 0x7fffffff:\n",
    "            return res\n",
    "        num_bin = bin(num).replace('b', 'b0')[::-1]\n",
    "        idx = num_bin.find(\"10\")\n",
    "        ones = num_bin.count('1', 0, idx)\n",
    "        res[0] = int(('1' * ones + '0' * (idx - ones) + \"01\" + num_bin[idx + 2:])[::-1], base=2)\n",
    "        idx = num_bin.find(\"01\")\n",
    "        if idx != -1:\n",
    "            ones = num_bin.count('1', 0, idx)\n",
    "            res[1] = int(('0' * (idx - ones) + '1' * ones + \"10\" + num_bin[idx + 2:])[::-1], base=2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        res = [-1] * 2\n",
    "        if num == 0x7fffffff:\n",
    "            return res\n",
    "        num_bin = bin(num).replace('b', 'b0')[::-1]\n",
    "        idx = num_bin.find(\"10\")\n",
    "        ones = num_bin.count('1', 0, idx)\n",
    "        res[0] = int(('1' * ones + '0' * (idx - ones) + \"01\" + num_bin[idx + 2:])[::-1], base=2)\n",
    "        idx = num_bin.find(\"01\")\n",
    "        if idx != -1:\n",
    "            ones = num_bin.count('1', 0, idx)\n",
    "            res[1] = int(('0' * (idx - ones) + '1' * ones + \"10\" + num_bin[idx + 2:])[::-1], base=2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_small(self, bit1):\n",
    "        # 找出第一个1且其左边还有0\n",
    "        loc1 = -1\n",
    "        loc0 = -1\n",
    "        for i in range(len(bit1)):\n",
    "            if bit1[i]==1 and 0 in bit1[:i]:\n",
    "                loc1 = i\n",
    "                break\n",
    "        # 找到左边离这个1最近的0\n",
    "        for i in range(loc1):\n",
    "            if bit1[i]==0:\n",
    "                loc0 = i\n",
    "        small = 0\n",
    "        if loc0==-1 or loc1 == -1: # 如果没有找到\n",
    "            small = -1\n",
    "        else: # 找到了\n",
    "            # 将最低位的1交换到最高位的0\n",
    "            bit1[loc0] = 1\n",
    "            bit1[loc1] = 0\n",
    "            # 将低于loc0位的1与0交换\n",
    "            low, high = 0, loc0-1\n",
    "            while low<high:\n",
    "                if bit1[low] == 1:\n",
    "                    while high>low:\n",
    "                        if bit1[high]==0:\n",
    "                            bit1[high]=1\n",
    "                            bit1[low]=0\n",
    "                            low+=1\n",
    "                            high-=1\n",
    "                            break\n",
    "                        high-=1\n",
    "                else:\n",
    "                    low+=1\n",
    "\n",
    "            for i in range(len(bit1)):\n",
    "                small += bit1[i]<<i\n",
    "        return small\n",
    "\n",
    "    def get_big(self, bit1):\n",
    "        # 找出第一个0且其左边有1\n",
    "        loc1 = -1\n",
    "        loc0 = -1\n",
    "        for i in range(len(bit1)):\n",
    "            if bit1[i]==0 and 1 in bit1[:i]:\n",
    "                loc0 = i\n",
    "                break\n",
    "\n",
    "        # 找出离这个0最近的1\n",
    "        for i in range(loc0):\n",
    "            if bit1[i]==1:\n",
    "                loc1 = i\n",
    "        \n",
    "        big = 0\n",
    "        if loc0==-1 or loc1 == -1:\n",
    "            big = -1\n",
    "        else:\n",
    "            bit1[loc0] = 1\n",
    "            bit1[loc1] = 0\n",
    "            # 将低于loc0位的1与0交换\n",
    "            low, high = 0, loc0-1\n",
    "            while low<high:\n",
    "                if bit1[low] == 0:\n",
    "                    while high>low:\n",
    "                        if bit1[high]==1:\n",
    "                            bit1[high]=0\n",
    "                            bit1[low]=1\n",
    "                            low+=1\n",
    "                            high-=1\n",
    "                            break\n",
    "                        high-=1\n",
    "                else:\n",
    "                    low+=1\n",
    "            for i in range(len(bit1)):\n",
    "                big += bit1[i]<<i\n",
    "\n",
    "        return big\n",
    "\n",
    "\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        bit1 = [0]*31\n",
    "        for i in range(len(bit1)):\n",
    "            if num & 1<<i != 0: \n",
    "                bit1[i]=1\n",
    "        small = self.get_small(bit1[:])\n",
    "        big = self.get_big(bit1[:])\n",
    "        \n",
    "        return [big, small] \n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_small(self, bit1):\n",
    "        # 找出第一个1且其左边还有0\n",
    "        loc1 = -1\n",
    "        loc0 = -1\n",
    "        for i in range(len(bit1)):\n",
    "            if bit1[i]==1 and 0 in bit1[:i]:\n",
    "                loc1 = i\n",
    "                break\n",
    "        # 找到左边离这个1最近的0\n",
    "        for i in range(loc1):\n",
    "            if bit1[i]==0:\n",
    "                loc0 = i\n",
    "        small = 0\n",
    "        if loc0==-1 or loc1 == -1: # 如果没有找到\n",
    "            small = -1\n",
    "        else: # 找到了\n",
    "            # 将最低位的1交换到最高位的0\n",
    "            bit1[loc0] = 1\n",
    "            bit1[loc1] = 0\n",
    "            # 将低于loc0位的1与0交换(把1交换到高位，相距最远的0和1交换)\n",
    "            low, high = 0, loc0-1\n",
    "            while low<high:\n",
    "                if bit1[low] == 1:\n",
    "                    while high>low:\n",
    "                        if bit1[high]==0:\n",
    "                            bit1[high]=1\n",
    "                            bit1[low]=0\n",
    "                            low+=1\n",
    "                            high-=1\n",
    "                            break\n",
    "                        high-=1\n",
    "                else:\n",
    "                    low+=1\n",
    "\n",
    "            for i in range(len(bit1)):\n",
    "                small += bit1[i]<<i\n",
    "        return small\n",
    "\n",
    "    def get_big(self, bit1):\n",
    "        # 找出第一个0且其左边有1\n",
    "        loc1 = -1\n",
    "        loc0 = -1\n",
    "        for i in range(len(bit1)):\n",
    "            if bit1[i]==0 and 1 in bit1[:i]:\n",
    "                loc0 = i\n",
    "                break\n",
    "\n",
    "        # 找出离这个0最近的1\n",
    "        for i in range(loc0):\n",
    "            if bit1[i]==1:\n",
    "                loc1 = i\n",
    "        \n",
    "        big = 0\n",
    "        if loc0==-1 or loc1 == -1:\n",
    "            big = -1\n",
    "        else:\n",
    "            bit1[loc0] = 1\n",
    "            bit1[loc1] = 0\n",
    "            # 将低于loc0位的1与0交换(把1交换到低位，相距最远的0和1交换)\n",
    "            low, high = 0, loc0-1\n",
    "            while low<high:\n",
    "                if bit1[low] == 0:\n",
    "                    while high>low:\n",
    "                        if bit1[high]==1:\n",
    "                            bit1[high]=0\n",
    "                            bit1[low]=1\n",
    "                            low+=1\n",
    "                            high-=1\n",
    "                            break\n",
    "                        high-=1\n",
    "                else:\n",
    "                    low+=1\n",
    "            for i in range(len(bit1)):\n",
    "                big += bit1[i]<<i\n",
    "\n",
    "        return big\n",
    "\n",
    "\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        bit1 = [0]*31\n",
    "        for i in range(len(bit1)):\n",
    "            if num & 1<<i != 0: \n",
    "                bit1[i]=1\n",
    "        small = self.get_small(bit1[:])\n",
    "        big = self.get_big(bit1[:])\n",
    "        return [big, small] \n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_small(self, bit1):\n",
    "        # 找出第一个1且其左边还有0\n",
    "        loc1 = -1\n",
    "        loc0 = -1\n",
    "        for i in range(len(bit1)):\n",
    "            if bit1[i]==1 and 0 in bit1[:i]:\n",
    "                loc1 = i\n",
    "                break\n",
    "        # 找到左边离这个1最近的0\n",
    "        for i in range(loc1):\n",
    "            if bit1[i]==0:\n",
    "                loc0 = i\n",
    "        small = 0\n",
    "        if loc0==-1 or loc1 == -1: # 如果没有找到\n",
    "            small = -1\n",
    "        else: # 找到了\n",
    "            # 将最低位的1交换到最高位的0\n",
    "            bit1[loc0] = 1\n",
    "            bit1[loc1] = 0\n",
    "            # 将低于loc0位的1与0交换\n",
    "            low, high = 0, loc0-1\n",
    "            while low<high:\n",
    "                if bit1[low] == 1:\n",
    "                    while high>low:\n",
    "                        if bit1[high]==0:\n",
    "                            bit1[high]=1\n",
    "                            bit1[low]=0\n",
    "                            low+=1\n",
    "                            high-=1\n",
    "                            break\n",
    "                        high-=1\n",
    "                else:\n",
    "                    low+=1\n",
    "\n",
    "            for i in range(len(bit1)):\n",
    "                small += bit1[i]<<i\n",
    "        return small\n",
    "\n",
    "    def get_big(self, bit1):\n",
    "        # 找出第一个0且其左边有1\n",
    "        loc1 = -1\n",
    "        loc0 = -1\n",
    "        for i in range(len(bit1)):\n",
    "            if bit1[i]==0 and 1 in bit1[:i]:\n",
    "                loc0 = i\n",
    "                break\n",
    "\n",
    "        # 找出离这个0最近的1\n",
    "        for i in range(loc0):\n",
    "            if bit1[i]==1:\n",
    "                loc1 = i\n",
    "        \n",
    "        big = 0\n",
    "        if loc0==-1 or loc1 == -1:\n",
    "            big = -1\n",
    "        else:\n",
    "            bit1[loc0] = 1\n",
    "            bit1[loc1] = 0\n",
    "            # 将低于loc0位的1与0交换\n",
    "            low, high = 0, loc0-1\n",
    "            while low<high:\n",
    "                if bit1[low] == 0:\n",
    "                    while high>low:\n",
    "                        if bit1[high]==1:\n",
    "                            bit1[high]=0\n",
    "                            bit1[low]=1\n",
    "                            low+=1\n",
    "                            high-=1\n",
    "                            break\n",
    "                        high-=1\n",
    "                else:\n",
    "                    low+=1\n",
    "            for i in range(len(bit1)):\n",
    "                big += bit1[i]<<i\n",
    "\n",
    "        return big\n",
    "\n",
    "\n",
    "\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        bit1 = [0]*31\n",
    "        for i in range(len(bit1)):\n",
    "            if num & 1<<i != 0: \n",
    "                bit1[i]=1\n",
    "        print(bit1)\n",
    "        small = self.get_small(bit1[:])\n",
    "        big = self.get_big(bit1[:])\n",
    "        \n",
    "        return [big, small] \n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        res = [-1] * 2\n",
    "        ones = bits = 0\n",
    "        while bits < 31 and not (1 << bits & num):\n",
    "            bits += 1\n",
    "        while bits < 31 and 1 << bits & num:\n",
    "            bits += 1\n",
    "            ones += 1\n",
    "        if bits != 31:\n",
    "            res[0] = ((num | 1 << bits) & ~((1 << bits) - 1)) | ((1 << (ones - 1)) - 1)\n",
    "        ones = bits = 0\n",
    "        while bits < 31 and 1 << bits & num:\n",
    "            bits += 1\n",
    "            ones += 1\n",
    "        while bits < 31 and not (1 << bits & num):\n",
    "            bits += 1\n",
    "        if bits != 31:\n",
    "            res[1] = (num & ~(1 << bits) | ((1 << bits) - 1)) & ~((1 << (bits - ones - 1)) - 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        larger, smaller = [], []\n",
    "        temp = num\n",
    "        while temp != 0:\n",
    "            larger.append(temp % 2)\n",
    "            smaller.append(temp % 2)\n",
    "            temp //= 2\n",
    "        larger.append(0)\n",
    "        changed_smaller = False\n",
    "        for i in range(len(smaller) - 1):\n",
    "            if smaller[i] == 0 and smaller[i + 1] == 1:\n",
    "                changed_smaller = True\n",
    "                smaller[i], smaller[i + 1] = 1, 0\n",
    "                num1 = sum(smaller[:i])\n",
    "                for j in range(i - 1, i - num1 - 1, -1):\n",
    "                    smaller[j] = 1\n",
    "                for j in range(i - num1 - 1, -1, -1):\n",
    "                    smaller[j] = 0\n",
    "                break\n",
    "        for i in range(1, len(larger)):\n",
    "            if larger[i] == 0 and larger[i - 1] == 1:\n",
    "                larger[i], larger[i - 1] = 1, 0\n",
    "                num1 = sum(larger[: i - 1])\n",
    "                for j in range(num1):\n",
    "                    larger[j] = 1\n",
    "                for j in range(num1, i - 1):\n",
    "                    larger[j] = 0\n",
    "                break\n",
    "        result = [0, -1]\n",
    "        temp = 1\n",
    "        for i in range(len(larger)):\n",
    "            result[0] += larger[i] * temp\n",
    "            temp *= 2\n",
    "        if result[0] >= 2**31:\n",
    "            result[0] = -1\n",
    "        if changed_smaller:\n",
    "            temp = 1\n",
    "            result[1] = 0\n",
    "            for i in range(len(smaller)):\n",
    "                result[1] += smaller[i] * temp\n",
    "                temp *= 2\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        ans = [-1, -1] # 默认无解\n",
    "        # 大于\n",
    "        i = 0 # 二进制数的第几位\n",
    "        count = 0 # 从右往左统计沿途遇见 1 的个数\n",
    "        while i < 31 and not (num & (1 << i)): # 跳过开头的 0，遇见 1 停 \n",
    "            i += 1\n",
    "        while i < 31 and (num & (1 << i)): # 遇见 0 停止，同时统计 1 的个数 \n",
    "            count += 1\n",
    "            i += 1\n",
    "        if i < 31: # 未越界\n",
    "            rightone = 1 << i \n",
    "            nums = num ^ rightone # 将 i 位置的 0 改成 1\n",
    "            i -= 1\n",
    "            j = 0\n",
    "            while j <= i: # 在[0, i]位置放置 0 和 1\n",
    "                if count > 1:\n",
    "                    if not nums & (1<<j): # i位置不为1 ，需要改成1\n",
    "                        nums = nums ^ (1<<j)\n",
    "                else:\n",
    "                    if nums & (1<<i): # i位置不为0 ，需要改成0\n",
    "                        nums = nums&(~(1<<j))\n",
    "                count -= 1\n",
    "                j += 1\n",
    "            ans[0] = nums\n",
    "        # 小于\n",
    "        i = 0 # 二进制数的第几位\n",
    "        count = 0 # 从右往左统计沿途遇见 1 的个数\n",
    "        while i < 31 and (num & (1 << i)): # 跳过开头的 1，遇见 0 停，同时统计 1 的个数 \n",
    "            count += 1\n",
    "            i += 1\n",
    "        while i < 31 and not (num & (1 << i)): # 遇见 1 停止\n",
    "            i += 1\n",
    "        if i < 31: # 未越界\n",
    "            rightone = 1 << i\n",
    "            num = num & (~rightone) # 将i位置的1 改成0\n",
    "            i -= 1\n",
    "            while i >= 0:  # 在[0, i]位置放置 0 和 1\n",
    "                if count >= 0:\n",
    "                    if not num & (1<<i): # i位置不为1 ，需要改成1\n",
    "                        num = num ^ (1<<i)\n",
    "                else:\n",
    "                    if num & (1<<i): # i位置不为0 ，需要改成0\n",
    "                        num = num&(~(1<<i))\n",
    "                count -= 1\n",
    "                i -= 1\n",
    "            ans[1] = num\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "\n",
    "        mn, mx = 1, 2147483647\n",
    "\n",
    "\n",
    "\n",
    "        def findLarge(n):\n",
    "\n",
    "            # 从右开始找到第1个1\n",
    "\n",
    "            # 然后记录1的个数ones直到再遇到0或到最高位\n",
    "\n",
    "            # 然后将这个0变成1\n",
    "\n",
    "            # 然后右边的位数用000...111(ones-1个1)填充\n",
    "\n",
    "            checkMask = 1\n",
    "\n",
    "            bits = 0\n",
    "\n",
    "            while checkMask <= n and checkMask & n == 0:\n",
    "\n",
    "                checkMask <<= 1\n",
    "\n",
    "                bits += 1\n",
    "\n",
    "            ones = 0  # 直接构造出000...111\n",
    "\n",
    "            while checkMask <= n and checkMask & n != 0:\n",
    "\n",
    "                ones = (ones << 1) + 1\n",
    "\n",
    "                checkMask <<= 1\n",
    "\n",
    "                bits += 1\n",
    "\n",
    "            # 因为在改变的位已经将1个0转成1了, 所以这里ones要向右移动一位\n",
    "\n",
    "            ones >>= 1\n",
    "\n",
    "            # 将0转成1\n",
    "\n",
    "            n |= checkMask\n",
    "\n",
    "            # 清除右边的0\n",
    "\n",
    "            n = (n >> bits) << bits\n",
    "\n",
    "            # 将右边填充上ones\n",
    "\n",
    "            n |= ones\n",
    "\n",
    "            return n if mn <= n <= mx else -1\n",
    "\n",
    "\n",
    "\n",
    "        def findSmall(n):\n",
    "\n",
    "            # 从右开始找到第1个0, 记录此过程1的个数ones\n",
    "\n",
    "            # 然后继续往左找直到再遇到1\n",
    "\n",
    "            # 然后将这个1变成0, ones也要左移一位(也可以初始化为1)\n",
    "\n",
    "            # 然后右边的位数用高位ones个1填充, 即构造出111...000, 可以直接基于ones构造\n",
    "\n",
    "            # 注意如果全为1的话是无解的, 直接返回-1\n",
    "\n",
    "            checkMask = 1\n",
    "\n",
    "            bits = 0\n",
    "\n",
    "            ones = 1\n",
    "\n",
    "            while checkMask <= n and checkMask & n != 0:\n",
    "\n",
    "                checkMask <<= 1\n",
    "\n",
    "                bits += 1\n",
    "\n",
    "                ones = (ones << 1) + 1\n",
    "\n",
    "            if checkMask > n:\n",
    "\n",
    "                # 全部是1\n",
    "\n",
    "                return -1\n",
    "\n",
    "            while checkMask <= n and checkMask & n == 0:\n",
    "\n",
    "                checkMask <<= 1\n",
    "\n",
    "                bits += 1\n",
    "\n",
    "                ones <<= 1\n",
    "\n",
    "            # 因为ones初始化为1, 所以ones需要右移一位\n",
    "\n",
    "            ones >>= 1\n",
    "\n",
    "            # 将需要改变的1变成0\n",
    "\n",
    "            n &= ~checkMask\n",
    "\n",
    "            # 清除右边的0\n",
    "\n",
    "            n = (n >> bits) << bits\n",
    "\n",
    "            # 将右边填充上ones\n",
    "\n",
    "            n |= ones\n",
    "\n",
    "            return n if mn <= n <= mx else -1\n",
    "\n",
    "\n",
    "\n",
    "        return [findLarge(num), findSmall(num)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        def findlarger(num):\n",
    "            mask = 1\n",
    "            bits = 0\n",
    "            while mask <= num and mask & num == 0:\n",
    "                mask <<= 1\n",
    "                bits += 1      \n",
    "            ones = 0\n",
    "            while mask <= num and mask & num != 0:\n",
    "                mask <<= 1\n",
    "                ones = (ones<<1)+1\n",
    "                bits += 1\n",
    "            num = num>>(bits)<<(bits)\n",
    "            num |= mask\n",
    "            num += ones>>1\n",
    "            return num if 1 <= num <= 1<<31 else -1\n",
    "\n",
    "        def findsmaller(num):\n",
    "            mask = 1\n",
    "            bits = 0\n",
    "            ones = 1\n",
    "            while mask <= num and mask & num != 0:\n",
    "                ones = (ones<<1)+1\n",
    "                bits += 1\n",
    "                mask <<= 1\n",
    "            if mask > num:\n",
    "                return -1\n",
    "            while mask <= num and mask & num == 0:\n",
    "                bits += 1\n",
    "                mask <<= 1\n",
    "                ones <<= 1\n",
    "            \n",
    "            num = (num>>bits)<<bits\n",
    "            num ^= mask\n",
    "            num += ones>>1\n",
    "            return num\n",
    "\n",
    "        # print(findlarger(num))\n",
    "        return [findlarger(num), findsmaller(num)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        \"\"\"\n",
    "        变大：最后一个01变为10，后续1右靠，未找到返回-1\n",
    "        变小：最后一个10变为01，后续1左靠，未找到返回-1\n",
    "        \"\"\"\n",
    "        remin, remax = 0,0\n",
    "        imin,flag,imin1 = 0, False, 0\n",
    "        for i in range(32):\n",
    "            acc = (num>>i)&1\n",
    "            if not flag and acc==0:\n",
    "                flag = True\n",
    "            if acc==1:\n",
    "                if not flag:\n",
    "                    imin1+=1\n",
    "                else:\n",
    "                    imin = i\n",
    "                    break\n",
    "        remin = ((num^(1<<imin))&(~((1<<imin)-1)))|(((1<<(imin1+1))-1)<<(imin-imin1-1)) if imin>imin1 else -1\n",
    "        flag, imax, imax1 = False, 0, 0\n",
    "        for i in range(32):\n",
    "            acc = (num>>i)&1\n",
    "            if acc==1:\n",
    "                imax1+=1\n",
    "                flag = True\n",
    "            if flag and acc==0:\n",
    "                imax = i\n",
    "                break\n",
    "        remax = ((num|(1<<imax))&(~((1<<imax)-1)))|((1<<(imax1-1))-1) if imax<31 else -1\n",
    "        return [remax,remin]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_small(self, bit1):\n",
    "        # 找出第一个1且其左边还有0\n",
    "        loc1 = -1\n",
    "        loc0 = -1\n",
    "        for i in range(len(bit1)):\n",
    "            if bit1[i]==1 and 0 in bit1[:i]:\n",
    "                loc1 = i\n",
    "                break\n",
    "        # 找到左边离这个1最近的0\n",
    "        for i in range(loc1):\n",
    "            if bit1[i]==0:\n",
    "                loc0 = i\n",
    "        small = 0\n",
    "        if loc0==-1 or loc1 == -1: # 如果没有找到\n",
    "            small = -1\n",
    "        else: # 找到了\n",
    "            # 将最低位的1交换到最高位的0\n",
    "            bit1[loc0] = 1\n",
    "            bit1[loc1] = 0\n",
    "            # 将低于loc0位的1与0交换\n",
    "            low, high = 0, loc0-1\n",
    "            while low<high:\n",
    "                if bit1[low] == 1:\n",
    "                    while high>low:\n",
    "                        if bit1[high]==0:\n",
    "                            bit1[high]=1\n",
    "                            bit1[low]=0\n",
    "                            low+=1\n",
    "                            high-=1\n",
    "                            break\n",
    "                        high-=1\n",
    "                else:\n",
    "                    low+=1\n",
    "\n",
    "            for i in range(len(bit1)):\n",
    "                small += bit1[i]<<i\n",
    "        return small\n",
    "\n",
    "    def get_big(self, bit1):\n",
    "        # 找出第一个0且其左边有1\n",
    "        loc1 = -1\n",
    "        loc0 = -1\n",
    "        for i in range(len(bit1)):\n",
    "            if bit1[i]==0 and 1 in bit1[:i]:\n",
    "                loc0 = i\n",
    "                break\n",
    "\n",
    "        # 找出离这个0最近的1\n",
    "        for i in range(loc0):\n",
    "            if bit1[i]==1:\n",
    "                loc1 = i\n",
    "        \n",
    "        big = 0\n",
    "        if loc0==-1 or loc1 == -1:\n",
    "            big = -1\n",
    "        else:\n",
    "            bit1[loc0] = 1\n",
    "            bit1[loc1] = 0\n",
    "            # 将低于loc0位的1与0交换\n",
    "            low, high = 0, loc0-1\n",
    "            while low<high:\n",
    "                if bit1[low] == 0:\n",
    "                    while high>low:\n",
    "                        if bit1[high]==1:\n",
    "                            bit1[high]=0\n",
    "                            bit1[low]=1\n",
    "                            low+=1\n",
    "                            high-=1\n",
    "                            break\n",
    "                        high-=1\n",
    "                else:\n",
    "                    low+=1\n",
    "            for i in range(len(bit1)):\n",
    "                big += bit1[i]<<i\n",
    "\n",
    "        return big\n",
    "\n",
    "\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        bit1 = [0]*31\n",
    "        for i in range(len(bit1)):\n",
    "            if num & 1<<i != 0: \n",
    "                bit1[i]=1\n",
    "        small = self.get_small(bit1[:])\n",
    "        big = self.get_big(bit1[:])\n",
    "        return [big, small] \n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        b=str(bin(num))[2:]\n",
    "        if not '0' in b:\n",
    "            if len(b)==31:\n",
    "                return [-1,-1]\n",
    "            else:\n",
    "                return [int('0b10'+b[1:],2),-1]\n",
    "        b='0'+b\n",
    "        smaller,bigger=None,None\n",
    "        for i in range(len(b) - 1, -1, -1):\n",
    "            if b[i:i + 2] == '10':\n",
    "                tmp = b[i+2:]\n",
    "                tmp = '1' * tmp.count('1') + '0' * tmp.count('0')\n",
    "                smaller = b[:i] + '01' + tmp\n",
    "                break\n",
    "        for i in range(len(b) - 1, -1, -1):\n",
    "            if b[i:i + 2] == '01':\n",
    "                tmp = b[i+2:]\n",
    "                tmp = '0' * tmp.count('0') + '1' * tmp.count('1')\n",
    "                bigger = b[:i] + '10' + tmp\n",
    "                break\n",
    "        return [int(bigger, 2), int(smaller, 2)]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        mn, mx = 1, 2147483647\n",
    "\n",
    "        def findLarge(n):\n",
    "            checkMask = 1\n",
    "            bits = 0\n",
    "            while checkMask <= n and checkMask & n == 0:\n",
    "                checkMask <<= 1\n",
    "                bits += 1\n",
    "            ones = 0  # 直接构造出000...111\n",
    "            while checkMask <= n and checkMask & n != 0:\n",
    "                ones = (ones << 1) + 1\n",
    "                checkMask <<= 1\n",
    "                bits += 1\n",
    "            ones >>= 1\n",
    "            n |= checkMask\n",
    "            n = (n >> bits) << bits\n",
    "            n |= ones\n",
    "            return n if mn <= n <= mx else -1\n",
    "\n",
    "        def findSmall(n):\n",
    "            checkMask = 1\n",
    "            bits = 0\n",
    "            ones = 1\n",
    "            while checkMask <= n and checkMask & n != 0:\n",
    "                checkMask <<= 1\n",
    "                bits += 1\n",
    "                ones = (ones << 1) + 1\n",
    "            if checkMask > n:\n",
    "                return -1\n",
    "            while checkMask <= n and checkMask & n == 0:\n",
    "                checkMask <<= 1\n",
    "                bits += 1\n",
    "                ones <<= 1\n",
    "            ones >>= 1\n",
    "            n &= ~checkMask\n",
    "            n = (n >> bits) << bits\n",
    "            n |= ones\n",
    "            return n if mn <= n <= mx else -1\n",
    "\n",
    "        return [findLarge(num), findSmall(num)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_small(self, bit1):\n",
    "        # 找出第一个1且其左边还有0\n",
    "        loc1 = -1\n",
    "        loc0 = -1\n",
    "        for i in range(len(bit1)):\n",
    "            if bit1[i]==1 and 0 in bit1[:i]:\n",
    "                loc1 = i\n",
    "                break\n",
    "        # 找到左边离这个1最近的0\n",
    "        for i in range(loc1):\n",
    "            if bit1[i]==0:\n",
    "                loc0 = i\n",
    "        small = 0\n",
    "        if loc0==-1 or loc1 == -1: # 如果没有找到\n",
    "            small = -1\n",
    "        else: # 找到了\n",
    "            # 将最低位的1交换到最高位的0\n",
    "            bit1[loc0] = 1\n",
    "            bit1[loc1] = 0\n",
    "            # 将低于loc0位的1与0交换(把1交换到高位，相距最远的0和1交换)\n",
    "            low, high = 0, loc0-1\n",
    "            while low<high:\n",
    "                if bit1[low] == 1:\n",
    "                    while high>low:\n",
    "                        if bit1[high]==0:\n",
    "                            bit1[high]=1\n",
    "                            bit1[low]=0\n",
    "                            low+=1\n",
    "                            high-=1\n",
    "                            break\n",
    "                        high-=1\n",
    "                else:\n",
    "                    low+=1\n",
    "\n",
    "            for i in range(len(bit1)):\n",
    "                small += bit1[i]<<i\n",
    "        return small\n",
    "\n",
    "    def get_big(self, bit1):\n",
    "        # 找出第一个0且其左边有1\n",
    "        loc1 = -1\n",
    "        loc0 = -1\n",
    "        for i in range(len(bit1)):\n",
    "            if bit1[i]==0 and 1 in bit1[:i]:\n",
    "                loc0 = i\n",
    "                break\n",
    "\n",
    "        # 找出离这个0最近的1\n",
    "        for i in range(loc0):\n",
    "            if bit1[i]==1:\n",
    "                loc1 = i\n",
    "        \n",
    "        big = 0\n",
    "        if loc0==-1 or loc1 == -1:\n",
    "            big = -1\n",
    "        else:\n",
    "            bit1[loc0] = 1\n",
    "            bit1[loc1] = 0\n",
    "            # 将低于loc0位的1与0交换(把1交换到低位，相距最远的0和1交换)\n",
    "            low, high = 0, loc0-1\n",
    "            while low<high:\n",
    "                if bit1[low] == 0:\n",
    "                    while high>low:\n",
    "                        if bit1[high]==1:\n",
    "                            bit1[high]=0\n",
    "                            bit1[low]=1\n",
    "                            low+=1\n",
    "                            high-=1\n",
    "                            break\n",
    "                        high-=1\n",
    "                else:\n",
    "                    low+=1\n",
    "            for i in range(len(bit1)):\n",
    "                big += bit1[i]<<i\n",
    "\n",
    "        return big\n",
    "\n",
    "\n",
    "    def findClosedNumbers(self, num: int) -> List[int]:\n",
    "        bit1 = [0]*31\n",
    "        for i in range(len(bit1)):\n",
    "            if num & 1<<i != 0: \n",
    "                bit1[i]=1\n",
    "        small = self.get_small(bit1[:])\n",
    "        big = self.get_big(bit1[:])\n",
    "        return [big, small] \n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
